package com.zzh.manacher;

import java.util.Arrays;

public class Manacher {
    public static void main(String[] args) {
        int[] man = manacherArr("$#1#2#2#1#2#3#2#1#");
        System.out.println(Arrays.toString(man));
    }
    public static int[] manacherArr(String str){
        int[] P=new int[str.length()];
        char[] S=str.toCharArray();
        int len = S.length;
        int mx=1;
        int id=0;
        P[0] = 1;
        for (int i=1;i<len;i++){
            if (mx>i){
                P[i]=Math.min(P[2*id-i],mx-i);
            }else {
                P[i]=1;
            }
//            for (;(i-P[i]>=0)&&(i+P[i]<len)&&(S[i+P[i]]==S[i-P[i]]);P[i]++);
            while ((i-P[i]>=0)&&(i+P[i]<len)&&(S[i+P[i]]==S[i-P[i]])){
                P[i]++;
            }
            if (i+P[i]>mx){
                mx=i+P[i];
                id=i;
            }
        }
        return P;
    }
}
